/*
 * 双向链表
 * @Autor: wangxin
 * @Date: 2020-06-12 09:51:35
 * @LastEditTime: 2020-06-12 20:14:45
 */
/**
 * 双向链表节点类
 */
class DoublyNode {
  constructor(element) {
    this.element = element
    this.next = null
    this.prev = null
  }
}

/**
 * 双向链表类
 */
class DoublyLinkedList {
  constructor() {
    this.count = 0
    this.head = null
    this.tail = null
  }

  /**
   * 向链表尾部添加新元素
   */
  push(element) {
    const node = new DoublyNode(element)
    if (this.head == null) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    }
    this.count++
  }

  /**
   * 正向遍历并以字符串形式返回
   */
  toString() {
    if (this.head == null) {
      return ''
    }
    let objString = `${this.head.element}`
    let current = this.head.next
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${current.element}`
      current = current.next
    }
    return objString
  }

  /**
   * 获取指定位置数据
   */
  getElementAt(index) {
    if (index < 0 || index >= this.count) {
      return undefined
    }
    // 判断从头部开始找还是从尾部
    if (this.count / 2 > index) {
      let current = this.head
      for (let i = 0; i < index; i++) {
        current = current.next
      }
      return current
    } else if (this.count / 2 <= index) {
      let current = this.tail
      for (let i = this.count - 1; i > index; i--) {
        current = current.prev
      }
      return current
    }
  }

  /**
   * 在任意位置插入一个新元素
   */
  insert(element, index) {
    if (index < 0 || index > this.count) {
      return false
    }
    const node = new DoublyNode(element)
    let current = this.head
    if (index === 0) {
      if (this.head == null) {
        this.head = node
        this.tail = node
      } else {
        node.next = this.head
        current.prev = node
        this.head = node
      }
    } else if (index === this.count) {
      current = this.tail
      current.next = node
      node.prev = current
      this.tail = node
    } else {
      const previous = this.getElementAt(index - 1)
      current = previous.next
      node.next = current
      previous.next = node
      current.prev = node
      node.prev = previous
    }
    this.count++
    return true
  }

  /**
   * 从任意位置移除元素并返回
   */
  removeAt(index) {
    if (index < 0 || index >= this.count) {
      return undefined
    }
    // 被移除的项
    let current = this.head
    if (index === 0) {
      this.head = current.next
      if (this.count === 1) {
        this.tail = null
      } else {
        this.head.prev = null
      }
    } else if (index === this.count - 1) {
      current = this.tail
      this.tail = current.prev
      this.tail.next = null
    } else {
      current = this.getElementAt(index)
      const previous = current.prev
      previous.next = current.next
      current.next.prev = previous
    }
    this.count--
    return current.element
  }

  /**
   * 只移除指定的数据
   */
  remove(element) {
    let index = this.indexOf(element)
    this.removeAt(index)
  }

  /**
   * 返回指定数据的位置,没有找到返回-1
   */
  indexOf(element) {
    let current = this.head
    for (let i = 0; i < this.count; i++) {
      if (current.element === element) {
        return i
      }
      current = current.next
    }
    return -1
  }

  /**
   * 更新指定位置的数据
   */
  update(index, newElemnet) {
    if (index < 0 || index >= this.count) {
      return fasle
    }
    let current = this.getElementAt(index)
    current.element = newElemnet
    return true
  }

  /**
   * 是否为空
   */
  isEmpty() {
    return this.count === 0
  }

  /**
   * 返回链表长度
   */
  size() {
    return this.count
  }

  /**
   * 获取链表第一个元素
   */
  getHead() {
    return this.head.element
  }

  /**
   * 获取链表最后一个元素
   */
  getTail() {
    return this.tail.element
  }

  /**
   * 清空链表
   */
  clear() {
    this.count = 0
    this.head = null
    this.tail = null
  }
}

// 代码测试
// var list = new DoublyLinkedList()
// list.push(1)
// list.push(2)
// list.push(3)
// list.clear()
// console.log(list)
